#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int ElementType;

typedef struct STable
{
    ElementType *elem;
    int len;
} STable;

void InitSTable(STable &table, int len)
{
    table.elem = (ElementType *)malloc(sizeof(ElementType));
    table.len = len;
    srand(time(NULL));
    for (int i = 0; i < len; i++)
    {
        table.elem[i] = rand() % 100;
    }
}

void PrintSTable(STable table)
{
    for (int i = 0; i < table.len; i++)
    {
        printf("%3d", table.elem[i]);
    }
    printf("\n");
}

void Swap(ElementType &a, ElementType &b)
{
    ElementType tmp = a;
    a = b;
    b = tmp;
}

void HeapSortHelp(ElementType elem[], int root_index, int len)
{
    int dad = root_index;
    int son = dad * 2 + 1;
    while (son < len)
    {
        if (son + 1 < len && elem[son + 1] > elem[son])
        {
            son++;
        }
        if (elem[dad] < elem[son])
        {
            Swap(elem[dad], elem[son]);
            dad = son;
            son = dad * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

bool HeapSort(ElementType elem[], int len)
{
    // 构建大顶堆
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        HeapSortHelp(elem, i, len);
    }
    for (int i = len - 1; i > 0; i--)
    {
        Swap(elem[0], elem[i]);
        HeapSortHelp(elem, 0, i);
    }
    return true;
}

void MergeSortHelp(ElementType elem[], int left, int mid, int right)
{
    int left_index = left, right_index = mid + 1, index = left;
    ElementType new_elem[right + 1];
    for (int i = left; i <= right; i++)
    {
        new_elem[i] = elem[i];
    }
    while (left_index <= mid && right_index <= right)
    {
        if (new_elem[left_index] <= new_elem[right_index])
        {
            elem[index++] = new_elem[left_index++];
        }
        else
        {
            elem[index++] = new_elem[right_index++];
        }
    }
    while (left_index <= mid)
    {
        elem[index++] = new_elem[left_index++];
    }
    while (right_index <= right)
    {
        elem[index++] = new_elem[right_index++];
    }
}

bool MergeSort(ElementType elem[], int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        MergeSort(elem, left, mid);
        MergeSort(elem, mid + 1, right);
        // 合并两个有序数组
        MergeSortHelp(elem, left, mid, right);
    }
    return true;
}

int QuickSortHelp(ElementType elem[], int left, int right)
{
    ElementType flag = elem[left];
    while (left < right)
    {
        while (left < right && elem[right] >= flag)
        {
            right--;
        }
        elem[left] = elem[right];
        while (left < right && elem[left] <= flag)
        {
            left++;
        }
        elem[right] = elem[left];
    }
    elem[left] = flag;
    return left;
}

bool QuickSort(ElementType elem[], int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = QuickSortHelp(elem, left, right);
        QuickSort(elem, left, mid - 1);
        QuickSort(elem, mid + 1, right);
    }
    return true;
}

int main()
{
    STable table;
    InitSTable(table, 15);
    ElementType *new_elem;
    memcpy(new_elem, table.elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    printf("-----------------HeapSort------------------------\n");
    HeapSort(table.elem, table.len);
    PrintSTable(table);
    memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    printf("-----------------MergeSort------------------------\n");
    MergeSort(table.elem, 0, table.len - 1);
    PrintSTable(table);
    memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    printf("-----------------QuickSort------------------------\n");
    QuickSort(table.elem, 0, table.len - 1);
    PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    // PrintSTable(table);
    // printf("-----------------SelectSort------------------------\n");
    // SelectSort(table.elem, table.len);
    // PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    // PrintSTable(table);
    // printf("-----------------InsertSort------------------------\n");
    // InsertSort(table.elem, table.len);
    // PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    // PrintSTable(table);
    // printf("-----------------BobbleSort------------------------\n");
    // BobbleSort(table.elem, table.len);
    // PrintSTable(table);
    return 0;
}